package oj;

import java.util.HashMap;
import java.util.Map;

/**
 * @author 郝文雪
 * @date 2022/8/23 21:32
 * @Description Test
 */
public class LC437 {
    //map中key为节点的前缀和，value为前缀和的出现次数
    int target;
    Map<Long,Integer> map=new HashMap<>();
    public int pathSum(TreeNode root, int targetSum) {
        if(root==null) return 0;
        target=targetSum;
        map.put(0L,1);
        return dfs(root,0L);
    }

    /**
     * 节点B的前缀和-节点A的前缀和=target，说明节点A、B之间的节点的和为target
     * @param root
     * @param curSum
     * @return
     */
    private int dfs(TreeNode root,Long curSum){
        if(root==null) return 0;
        int res=0;//记录目标和的路径条数
        curSum+=root.val;//记录前缀和
        res+=map.getOrDefault(curSum-target,0);
        map.put(curSum,map.getOrDefault(curSum,0)+1);

        int left=dfs(root.left,curSum);
        int right=dfs(root.right,curSum);

        res=res+left+right;
        map.put(curSum,map.get(curSum)-1);
        return res;
    }
}
